package Elementary_algorithm.Other;

import org.junit.Test;

/*
缺失数字
给定一个包含 [0, n]中n个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：
输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

提示：
n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums 中的所有数字都 独一无二
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnj4mt/
 */
public class _06缺失数字 {

    @Test
    public void test() {
        System.out.println(missingNumber(new int[]{9,6,4,2,3,5,7,0,1}));
    }

    //方法四：数学 O(n) O(1)
    public int missingNumber(int[] nums) {
        int sum = 0;
        int tsum = 0;
        /*
        优化： 使用高斯求和公式求 1 ~ n 的和
        int total = n * (n + 1) / 2;
         */
        for (int i = 0; i < nums.length; i++) {
            tsum += i;
            sum += nums[i];
        }
        tsum += nums.length;
        return tsum - sum;
    }

    //其他方法
    /*
    方法一：排序 O(nlogn) O(logn)
    方法二：哈希集合 O(n) O(n)
    方法三：位运算 O(n) O(1)
     */

}
